МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра АСУ
Звіт із лабораторної роботи №13 «Градієнтний метод числової оптимізації задач нелінійного програмування» з дисципліни “Математичні методи дослідження операцій” Львів – 2012  Мета роботи: ознайомлення з градієнтним методом числової оптимізації, набуття навиків розв’язку та аналізу задач нелінійного програмування градієнтним методом. Короткі теоретичні відомості Градієнтні методи належать до наближених числових методів розв’язування задач нелінійного програмування, оскільки дають точний розв’язок за нескінченне і лише в окремих випадках за скінченне число кроків. З їх використанням можна розв’язувати будь-яку задачу нелінійного програмування, знаходячи, як правило, лише локальний екстремум. Тому застосування цих методів дає найбільший ефект для розв’язування задач випуклого програмування, де локальний екстремум є одночасно і глобальним. 1.1. Застосування градієнтного методу, коли обмеження на область зміни змінних х відсутні Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінних х відсутні. Пошук екстремального значення функції f(х) можна починати з будь-якого допустимого розв’язку, наприклад, з точки хk = (x1k; ...; хпk). Градієнтом (f(x) функції f(х) в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто
Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції f (х). Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої
. (1) де (k – числовий параметр, від величини якого залежить довжина кроку переміщення
. Величина (k, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції
(2) Чергову точку хk+1 визначаємо після обчислення параметру (k (для цього підставляємо значення (k в формулу (1) на пошуковій траєкторії). В цій ( хk+1 ) точці знову знаходимо градієнт, а рух відбувається далі по прямій хk+2 = хk+1 + (k+1(f(xk+1) у напрямку нового градієнту (f (xk+2) до точки хk+2, в якій досягається найбільше значення функції f(х) в цьому напрямку і т.д. Розв’язування триватиме доти, поки не буде досягнута точка х*, в якій градієнт функції дорівнює нулю. В цій точці х* цільова функція f(х*) і буде набувати максимального значення. Приклад 1. Нехай потрібно визначити точку максимуму функції
, коли процес розв’язування розпочинається з точки x0 = (4;4). Розв’язування. Знайдемо частинні похідні функції f(x)
;
. Градієнт функції в точці х0 буде
. Перемістимось з точки х0 вздовж градієнту (f(х0) в нову точку х1: х1 = x0 + λ0 (f (х0) = (4; 4) + (0 (–6; –4) = (4 – 6 (0; 4 – 4 (0). Градієнт функції в точці х1 дорівнює (f (х1) = [2 – 2 (4 – 6(0); 4 – 2 (4 – 4(0)] = (– 6 +12(0; – 4 + 8(0). З необхідної умови екстремуму одержуємо рівняння
, звідки
= 0,5. Оскільки
, то знайдене значення х1 є точкою максимуму функції (f (х1). Враховуючи
= 0,5, визначимо координати точки х1 на пошуковій траєкторії х1 = (4 – 6·0,5; 4 – 4·0,5) = (1; 2) та градієнт (f (х1) в цій точці х1 (f (х1) = (2 – 2·1; 4 – 2·2) = (0; 0). Оскільки градієнт (f (x1) має нульові координати, робимо висновок про те, що х1 = (1; 2) є точкою, в якій цільова функція досягає максимального значення f(х1) = 2·1+ 4·2 – 1– 4 = 5 ( в початковій точці f(x0) = – 8 ). На мал. 1 наведена графічна інтерпретація даної задачі.
Мал. 1. 1.2. Застосування градієнтного методу, коли наявні обмеження на область зміни змінних х Тепер розглянемо випадок розв’язування задачі нелінійного пр...